Strukturelle Analysen in der parallelen Komplexitätstheorie

Projektleitung und Mitarbeiter

Mittelgeber :

Forschungsbericht : 1994-1996

Tel./ Fax.:

Projektbeschreibung

Im Kern der Betrachtung stand hier das aus dem Bereich der formalen Sprachen bekannte Konzept der Eindeutigkeit. Eindeutigkeit läßt sich sinnvoll für Automaten und Schaltnetze definieren, findet aber auch seinen Widerklang im Bereich der parallelen Registermaschinen. So wurden beispielsweise enge Beziehungen hergestellt in dem Beziehungsgeflecht zwischen eindeutigen Schaltnetzen mit halbbeschränktem Eingangsgrad, eindeutig augmentierten Kellerautomaten und parallelen Registermaschinen mit exklusivem Schreibzugriff. Weitere in obigem Zusammenhang relevante Forschungspunkte waren lokal definierbare Akzeptaretypen bei Polynomzeit-Turingmaschinen, eindeutige Komplexitätshierarchien, das Konzept der leeren Alternierung und einiges mehr. Insgesamt läßt sich sagen, daß in diesem Bereich das reichhaltige Beziehungsgeflecht zwischen Klassen der parallelen Komplexitätstheorie einerseits weiter verfeinert, andererseits aber auch überraschende Übereinstimmungen und Inklusionen gezeigt werden konnten.

Publikationen

INDEX HOME SUCHEN KONTAKT LINKS